package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * <a href="https://leetcode.cn/problems/maximum-level-sum-of-a-binary-tree/">最大层内元素和(Maximum Level Sum of a Binary Tree)</a>
 * <p>给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。</p>
 * <p>请返回层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中 最小 的那个。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [1,7,0,7,-8,null,null]
 *      输出：2
 *      解释：
 *          第 1 层各元素之和为 1，
 *          第 2 层各元素之和为 7 + 0 = 7，
 *          第 3 层各元素之和为 7 + -8 = -1，
 *          所以我们返回第 2 层的层号，它的层内元素之和最大。
 *
 * 示例 2：
 *      输入：root = [989,null,10250,98693,-89388,null,null,null,-32127]
 *      输出：2
 * </pre>
 * </p>
 * <p>
 * <b>提示:</b>
 * <ul>
 *     <li>树中的节点数在 [1, 10^4]范围内</li>
 *     <li>-10^5 <= Node.val <= 10^5</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/13 15:22
 */
public class LC1161MaximumLevelSumOfBinaryTree_M {

    static class Solution {
        public int maxLevelSum(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int currLevel = 0;
            int maxVal = Integer.MIN_VALUE;
            int ans = 1;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                currLevel++;
                int currLevelNodeSize = queue.size();
                int currLevelNodeValSum = 0;
                for (int i = 0; i < currLevelNodeSize; i++) {
                    TreeNode currNode = queue.poll();
                    currLevelNodeValSum += currNode.val;
                    if (currNode.left != null) {
                        queue.offer(currNode.left);
                    }
                    if (currNode.right != null) {
                        queue.offer(currNode.right);
                    }
                }
                if (maxVal < currLevelNodeValSum) {
                    maxVal = currLevelNodeValSum;
                    ans = currLevel;
                }
            }
            return ans;
        }


        public int maxLevelSum2(TreeNode root) {
            // 假设从第0层开始。
            // 下标0对应着第0层所有元素的和，下标1对应着第一层第1层所有元素的和，...
            List<Integer> sumList = new ArrayList<>();
            dfs(root, 0, sumList);
            int ans = 0;
            for (int i = 0; i < sumList.size(); i++) {
                if (sumList.get(i) > sumList.get(ans)) {
                    ans = i;
                }
            }
            // 层号从 1 开始
            return ans + 1;
        }

        private void dfs(TreeNode node, int level, List<Integer> sumList) {
            if (node == null) {
                return;
            }
            // 进入到新的一层
            if (level == sumList.size()) {
                sumList.add(node.val);
            } else {
                // 当前层已存在：找到对应层，计算节点和
                sumList.set(level, sumList.get(level) + node.val);
            }
            if (node.left != null) {
                dfs(node.left, level + 1, sumList);
            }
            if (node.right != null) {
                dfs(node.right, level + 1, sumList);
            }
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(7);
        root1.right = new TreeNode(0);
        root1.left.left = new TreeNode(7);
        root1.left.right = new TreeNode(-8);

        TreeNode root2 = new TreeNode(989);
        root2.right = new TreeNode(10250);
        root2.right.left = new TreeNode(98693);
        root2.right.right = new TreeNode(-89388);
        root2.right.right.right = new TreeNode(-32127);

        Solution solution = new Solution();
        System.out.println(solution.maxLevelSum(root1));
        System.out.println(solution.maxLevelSum(root2));
    }
}
